#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <vector>
#include <set>
#include <queue>

using namespace std;
using LL = long long;
using PII = pair<int, int>;

vector<vector<LL>> mat_mul(vector<vector<LL>> a, vector<vector<LL>> b, LL mod){
    int n = a.size();
    vector<vector<LL>> res(n, vector<LL>(n));

    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            for(int k = 0; k < n; k ++){
                res[i][j] += a[i][k] * b[k][j];
                res[i][j] %= mod;
            }
        }
    }

    return res;
}


vector<vector<LL>> mat_pow(vector<vector<LL>> a, LL b, LL mod){

    int n = a.size();

    vector<vector<LL>> res(n, vector<LL>(n));

    for(int i = 0; i < n; i ++) res[i][i] = 1;

    while (b){
        if(b & 1) res = mat_mul(res, a, mod);
        a = mat_mul(a, a, mod);

        b >>= 1;
    }

    return res;
}

int main(){
#ifdef LOCALFLAG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif


    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    LL a, x, mod;
    cin >> a >> x >> mod;
    vector<vector<LL>> q = {{a, 1}, {0, 1}};
    vector<vector<LL>> res = mat_pow(q, x, mod);

    cout << res[0][1] << '\n';

    return 0;
}